package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC2122 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        int[] ans;
        int maxScore = Integer.MIN_VALUE;

        public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
            ans = new int[aliceArrows.length];
            int[] curTravel = new int[aliceArrows.length];
            backtrace(aliceArrows, aliceArrows.length - 1, numArrows, curTravel, 0);
            return ans;
        }

        public void backtrace(int[] aliceArrows, int i, int leftArrows, int[] curTravel, int curScore) {
            if (i < 0 || leftArrows <= 0) {
                if (curScore > maxScore) {
                    if (leftArrows > 0) curTravel[0] += leftArrows;
                    ans = Arrays.copyOf(curTravel, curTravel.length);
                    maxScore = curScore;
                }
                return;
            }
            // i 位置可以选也可以不选
            if (leftArrows >= aliceArrows[i] + 1) {
                curTravel[i] = aliceArrows[i] + 1;
                curScore += i;
                backtrace(aliceArrows, i - 1, leftArrows - aliceArrows[i] - 1, curTravel, curScore);
            }

            curScore -= leftArrows >= aliceArrows[i] + 1 ? i : 0;
            curTravel[i] = 0;
            backtrace(aliceArrows, i - 1, leftArrows, curTravel, curScore);
        }
    }

    public void run() {
        System.out.println(Arrays.toString(new Solution().maximumBobPoints(9, InputUtil.toIntegerArray("[1,1,0,1,0,0,2,1,0,1,2,0]"))));
        System.out.println(Arrays.toString(new Solution().maximumBobPoints(3, InputUtil.toIntegerArray("[0,0,1,0,0,0,0,0,0,0,0,2]"))));
        System.out.println(Arrays.toString(new Solution().maximumBobPoints(6, InputUtil.toIntegerArray("[0,0,1,1,2,1,0,0,0,0,1,0]"))));
        System.out.println(Arrays.toString(new Solution().maximumBobPoints(89, InputUtil.toIntegerArray("[3,2,28,1,7,1,16,7,3,13,3,5]"))));
    }

    public static void main(String[] args) throws Exception {
        LC2122 an = new LC2122();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
